The present invention relates generally to branch prediction in a computer processor, and more specifically, to confidence threshold-based opposing path execution for branch prediction.
A processor in a computer system may process an instruction by executing the instruction in a series of small steps, or operations. In some cases, to increase the number of instructions being processed by the processor, and therefore increase the speed of the processor, the processor may be pipelined. Pipelining refers to providing separate stages in a processor, wherein each stage performs one or more of the small steps necessary to execute an instruction. As an example of executing instructions in a pipeline, when a first instruction is received, a first pipeline stage may process a small part of the instruction. When the first pipeline stage has finished processing the small part of the instruction, a second pipeline stage may begin processing another small part of the first instruction while the first pipeline stage receives and begins processing a small part of a second instruction. Thus, the processor may process two or more instructions at the same time in parallel.
A computer program may include branch instructions, which cause the computer program to branch from one instruction to a target instruction (thereby skipping sequential instructions, if any) if a condition defined by the branch instruction is satisfied. If the condition is not satisfied, the next instruction sequentially after the branch instruction may be executed without branching to the target instruction. Typically, the outcome of the condition being tested is not known until the branch instruction is executed and its condition is tested. Thus, the correct next instruction to be executed after the branch instruction may not be known until the condition is tested.
Where a pipeline is utilized to execute instructions, the outcome of the branch instruction may not be known until branch resolution, after the branch instruction has passed through several stages of the pipeline. Thus, the correct next instruction to be executed after the branch instruction may not be known until the branch instruction has passed through the stages necessary to determine the outcome of the condition. In some cases, execution of instructions in the pipeline may be stalled (e.g., the stages of the pipeline preceding the branch instruction may not be used to execute instructions) until branch resolution. When the pipeline is stalled, the pipeline is not being used to execute as many instructions in parallel, decreasing overall processor efficiency.
In other cases, to improve processor efficiency, branch prediction may be used to predict the outcome of branch instructions. For example, when a branch instruction is encountered, the processor may predict which instruction, or path, will be executed after the outcome of the condition is known. Then, instead of stalling the pipeline when the branch instruction is issued, the processor may continue issuing instructions beginning with the predicted next instruction. The predicted path of a branch instruction may be referred to as the primary path, and the non-predicted path may be referred to as the opposing path.
However, in some cases, the branch prediction may be incorrect (e.g., the processor may predict one outcome of the branch instruction, but at branch resolution, the opposite outcome results). When the outcome of the branch instruction is mispredicted, the predicted instructions that were issued to the pipeline based on the branch prediction may be removed from the pipeline and the effects, which were to be checkpointed, of those instructions are undone. This is referred to as flushing the pipeline. Then, after the pipeline is flushed, the correct next instruction, corresponding to the opposing path, for the branch instruction may be issued to the pipeline and execution of the instructions may continue. When the outcome of a branch instruction is incorrectly predicted and the incorrectly predicted group of instructions corresponding to the primary path is flushed from the pipeline, thereby undoing previous work done by the pipeline, the efficiency of the processor may suffer.